These are notes on the method of normalized graph cuts and its applicationsto graph clustering. I provide a fairly thorough treatment of this deeplyoriginal method due to Shi and Malik, including complete proofs. I include thenecessary background on graphs and graph Laplacians. I then explain in detailhow the eigenvectors of the graph Laplacian can be used to draw a graph. Thisis an attractive application of graph Laplacians. The main thrust of this paperis the method of normalized cuts. I give a detailed account for K = 2 clusters,and also for K > 2 clusters, based on the work of Yu and Shi. Three points thatdo not appear to have been clearly articulated before are elaborated: 1. The solutions of the main optimization problem should be viewed as tuplesin the K-fold cartesian product of projective space RP^{N-1}. 2. When K > 2, the solutions of the relaxed problem should be viewed aselements of the Grassmannian G(K,N). 3. Two possible Riemannian distances are available to compare the closenessof solutions: (a) The distance on (RP^{N-1})^K. (b) The distance on theGrassmannian. I also clarify what should be the necessary and sufficient conditions for amatrix to represent a partition of the vertices of a graph to be clustered.
展开▼
